区间dp

一.概念

对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。

二.基本思路

阅读全文 »

伯努利数

伯努利数是一个用于解决 nn 次方和的数列。

它的递归定义公式如下:

i=0n(n+1i)Bi=[n=0]        (1.1)\sum_{i=0}^n \binom {n+1}{i} B_i=[n=0] ~~~~~~~~ (1.1)

阅读全文 »

LOJ528 求和

i=1nj=1mμ2(gcd(i,j))\sum_{i=1}^n\sum_{j=1}^m \mu^2(\gcd(i,j))

d=1min(n,m)μ2(d)i=1nj=1m[gcd(i,j)=d]\sum_{d=1}^{\min(n,m)}\mu^2(d)\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d]

阅读全文 »

P3703 [SDOI2017]树点涂色

众所周知,access(x)\text{access(x)}rtxrt \to x 这条实链在一个 splaysplay 中。也就是说, splaysplay 所维护的链中的点同色。

那么到点 xx 到根路径的权值便是经过虚边的数量 +1+1,不妨记为 disxdis_x